class Solution {
    vector<vector<string>> ret; //记录返回值
    vector<string> board;   //记录每一种可能的棋盘  
    bool used_col[9] = {false}; //用于记录每列是否存在皇后
    int _n;
    //画图，通过对角线的截距确定每条对角线的唯一性
    bool used_main_diagonal[2*9] = {false}; //用于记录每个主对角线是否存在皇后
    bool used_sub_diagonal[2*9] = {false};  //用于记录每个副对角线是否存在皇后

    //逐行分析
    void dfs(int row)
    {
        if (row >= _n)
        {
            ret.push_back(board);
            return;
        }

        string row_string;  //用来记录正确的行
        //逐列放置
        for (int j = 0; j < _n; j++)
        {   
            if (!used_col[j] && !used_main_diagonal[row - j + _n] && !used_sub_diagonal[row + j])
            {
                //拷贝一份，如果不满足，不会影响到原来的
                string row_string_bak = row_string;

                row_string_bak += 'Q';  //放置皇后
                row_string_bak += string(_n - j - 1, '.');
                board.push_back(row_string_bak);

                used_col[j] = true;
                used_main_diagonal[row - j + _n] = true;
                used_sub_diagonal[row + j] = true;

                dfs(row + 1);

                board.pop_back();
                used_col[j] = false;
                used_main_diagonal[row - j + _n] = false;
                used_sub_diagonal[row + j] = false;
                
                //如果无法达成条件，说明这一列不能放Q，直接放。
                row_string += '.';
            }
            else
                row_string += '.';
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        _n = n;
        dfs(0);

        return ret;
    }
};